/*
 * Copyright (C) 2013 Will Dignazio 
 * mstore.c
 */
#include "internal.h"
#include <openssl/sha.h>
#include <assert.h>
#include <pthread.h>

MNode*
allocnod(Error *err)
{
	MNode* node;

	node = calloc(1, sizeof(*node));
	if(node == NULL) {
		esys(err, "Failed to allocate node for mstore");
		return NULL;
	}

	return node;
}

MKey*
allockey(void* data, u64 len, Error *err)
{
	MKey* key;
	key = calloc(1, sizeof(*key));
	if(key == NULL) {
		esys(err, "Failed to allocate key for mstore");
		return NULL;
	}

	key->data = data;
	key->mid = mhash(data, len);

	return key;
}

MStore*
mstore_init(u64 minkeys, Error *err)
{
	MStore* mstore;
	MNode* hnode;

	mstore = NULL;

	if(err == NULL) {
		ewarn("Error object not set, required for construction");
		goto fail;
	}

        if(minkeys < 2) {
		error(err, "Too low minimal key count for mstore\n");
		goto fail;
	}

	mstore = calloc(1, sizeof(*mstore));
	if(mstore == NULL) {
		esys(err, "Calloc-ing instance for mstore");
		goto fail;
	}

	mstore->min = minkeys;

	hnode = allocnod(err);
	if(hnode == NULL)
		goto fail;

	mstore->nhead = hnode;
	hnode->khead = NULL;
	hnode->keys = 0;

	return mstore;

fail:
	if(mstore != NULL) {
		if(mstore->nhead != NULL)
			free(mstore->nhead);
		free(mstore);
	}

	return NULL;
}

int
keycmp(MKey* k1, MKey* k2)
{
	int cmp;
	cmp = mhashcmp(&k1->mid, &k2->mid);
	return cmp;
}

/* Search for hash within tree from given node */
MNode*
mstore_search_node(MNode* mn, MHash mid, void** data, Error *err)
{
	MKey* kcur;
	MNode* r;
	int c;

	r = mn;
	if(mn == NULL) {
		*data = NULL;
		goto done;
	}

	kcur = mn->khead;
	if(kcur == NULL) {
		*data = NULL;
		r = mstore_search_node(kcur->lcn, mid, data, err);
		goto done;
	}

	/* Found key */
	c = mhashcmp(&kcur->mid, &mid);
	if(c == 0) {
		*data = kcur->data;
		goto done;
	}

	while(kcur->next != NULL && mhashcmp(&kcur->mid, &mid) < 0)
		kcur = kcur->next;

	if(kcur->next) { // Search right
		if(kcur->rcn != NULL)
			r = mstore_search_node(kcur->rcn, mid, data, err);
	}
	else { // Search left
		if(kcur->lcn != NULL)
			r = mstore_search_node(kcur->lcn, mid, data, err);
	}

done:
	return r;
}

/* Search for hash within mstore */
int
mstore_search(void **data, MHash mid, MStore *ms, Error *err)
{
	MNode *mn;

	mn = mstore_search_node(ms->nhead, mid, data, err);
	if(mn == NULL)
		return 1;

	return 0;
}

/* Insert key into given Node */
static int
mstore_key_insert(MNode* mn, MKey* mk)
{
	MKey* kcur;

	/* First node in list */
	if(mn->khead == NULL) {
		assert(mn->keys == 0);
		mn->khead = mk;
		mk->prev = NULL;
		mk->next = NULL;
		goto out;
	}

	/* Insertion to front of list */
	if(keycmp(mn->khead, mk) > 0) {
		kcur = mn->khead;
		kcur->prev = mk;
		mk->next = kcur;
		mk->prev = NULL;

		kcur->lcn = mk->rcn;
		mk->node = kcur->node;
		mn->khead = mk;
		goto out;
	}

	/* We need to go deeper right */
	kcur = mn->khead;
	while(keycmp(mk, kcur) > 0) {
		if(keycmp(mn->khead, mk) == 0)
			return 1;
		if(kcur->next == NULL)
			break;

		if(keycmp(kcur->next, mk) > 0) // go one less
			break;

		kcur = kcur->next;
	}

	/* Last key in list */
	if(kcur->next == NULL) {
		kcur->next = mk;
		mk->prev = kcur;
		mk->next = NULL;
		mk->prev->next = mk;

		kcur->rcn = mk->lcn;
		mk->node = kcur->node;
		goto out;
	}

	/* In between two MKeys */
	assert(kcur != NULL);
	assert(kcur->next->prev == kcur);
	assert(keycmp(kcur, mk) < 0);

	mk->next = kcur->next;
	mk->prev = kcur;

	kcur->next = mk;
	mk->next->prev = mk;

	kcur->rcn = mk->lcn;
	mk->next->lcn = mk->rcn;

out:
	mk->node = mn;
	mn->keys++;

	return 0;
}

/* Rebalance MNode, return deriving parent key */
static MKey*
mstore_rebalance_node(MNode* node, u64 min, Error *err)
{
	MKey* pkey;
	MKey* tnext;
	MKey* tprev;
	MNode* newnode;
	MNode* ornode;
	int k;
	int r;

	k = 0;
	r = -1;

	newnode = allocnod(err);
	if(newnode == NULL)
		goto fail;

	pkey = node->khead;
	for(k=0; k<min; k++) // Go to middle key
		pkey = pkey->next;

	ornode = pkey->rcn;

	tnext = pkey->next;	// Orphaned Keys
	tprev = pkey->prev;	// Keys in old node

	/*
	 * Top level node needs to be rebalanced, and we
	 * need to create yet another new node.
	 */
	if(node->parent == NULL) {
		MNode* newtop;

		newtop = allocnod(err);
		if(newtop == NULL)
			goto fail;

		node->parent = newtop;
	}

	/*
	 * We need to set this up now, so that upon
	 * insertion, the lcn and rcn are put into the node
	 * up with mstore_key_insert.
	 */
	pkey->lcn = tprev->node;
	pkey->rcn = newnode;

	r = mstore_key_insert(node->parent, pkey);
	if(r != 0) {
		error(err, "Failed to insert key into parent: %d\n", r);
		goto fail;
	}

	assert(tnext != NULL);
	tnext->prev = NULL; // Seperate it out
	tnext->lcn = ornode; // Premptively assign left node

	/* Transfer keys over to new node (On right side). */
	MKey* rnext = tnext;
	while(tnext != NULL && rnext != NULL) {
		rnext = rnext->next;

		r = mstore_key_insert(newnode, tnext);
		if(r != 0) {
			error(err, "Failed to insert new key into node: %d\n", r);
			goto fail;
		}

		tnext = rnext;
	}
	newnode->parent = node->parent;

	/* Solidify the left side keys (from node passed in) */
	tprev->next = NULL;
	tprev->node->keys = min;

	return pkey;

fail:
	if(newnode != NULL)
		free(newnode);
	return NULL;
}

int
mstore_remove(MStore* ms, MHash mid, Error *err)
{
	MNode *mn;
	void *data;
	int ret;

	ret = -1;

	mn = mstore_search_node(ms->nhead, mid, &data, err);
	if(mn == NULL)
		goto out;

out:
	return ret;
}

int
mstore_insert(void *obj, u64 len, MStore *ms, Error *err)
{
	MKey* nkey;
	MNode* fnode;
	void* tobj;
	int r;

	tobj = NULL;
	fnode = NULL;
	r = -1;

	if(obj == NULL || len == 0 || ms == NULL)
		goto out;

	nkey = allockey(obj, len, err);
	if(nkey == NULL)
		goto out;

	if(ms->nhead->khead == NULL) { // New tree
		ms->nhead->khead = nkey;
		ms->nhead->keys++;
		nkey->node = ms->nhead;
		r = 0;
		goto out;
	}

	fnode = mstore_search_node(ms->nhead, nkey->mid, &tobj, err);
	if(tobj != NULL) // Insertion of already existant node
		goto out;

	if(fnode == NULL) // New head
		fnode = ms->nhead;

	r = mstore_key_insert(fnode, nkey);
	if(r != 0)
		goto out;

	/*
	 * A rebalance is required to sort things
	 * out within the btree.
	 */
	MKey* refkey = nkey;
	while(fnode != NULL && fnode->keys > (ms->min*2)) {
		refkey = mstore_rebalance_node(fnode, ms->min, err);
		if(fnode == ms->nhead) // replace it with the resulting node
			ms->nhead = refkey->node;

		fnode = fnode->parent;
	}

	r = 0;
out:
	return r;
}

/* Node is a leaf on the BTree */
static int
isleaf(MNode* nod)
{
	/* This should technically be the top node empty */
	if(nod->khead == NULL)
		return 1;

	if(nod->khead->lcn == NULL &&
	   nod->khead->rcn == NULL)
		return 1;

	return 0;
}

/* Get a key within a node */
static MKey*
getkey(MNode *mnod, MHash *hash) 
{
	MKey *key;

	key = mnod->khead;
	while(mhashcmp(&key->mid, hash) != 0)
		key = key->next;

	return key;
}

static MKey*
parentkey(MNode *mnod, MHash *hash)
{
	MKey *key;
	key = mnod->khead;
	printf("node has %lu keys\n", mnod->keys);
	while(mhashcmp(hash, &key->mid) > 0 && key->next != NULL) {
		printf("iterating forward\n");
		key = key->next;
	}
	if(key->rcn == mnod)
		printf("... :(\n");
	return key;
}

int
mstore_delete(MHash *mid, MStore *mstore, Error *err)
{
	MNode *pnod;
	MNode *bnod;
	MKey *key;
	void *data;
	int lminimal;
	int rminimal;
	int ret;

	ret = -1;
	lminimal = 0;
	rminimal = 0;
	pnod = NULL;
	key = NULL;

	bnod = mstore_search_node(mstore->nhead, *mid, &data, err);
	if(bnod == NULL) // Does not exist in mstore
		goto done;

	key = getkey(bnod, mid);

	if(isleaf(bnod)) {
		MKey *pkey;

		printf("Leaf key deletion.\n");
		/* Case 1: Leaf node and has > minimum keys */
		if(bnod->keys > mstore->min) {
			printf("Case #1: Remove leaf with > minkeys (was %lu)\n", bnod->keys);
			key->prev->next = key->next;
			goto done;
		}

		/*
		 * Case 2: Leaf node has < minimum keys, but
		 * adjacent node has extra.
		 */
		printf("Case #2: Remove leaf with < minkeys (was %lu)\n", bnod->keys);
		pkey = parentkey(bnod->parent, mid); // Check Right
		if(pkey->rcn->keys > mstore->min && pkey->rcn != bnod) {
			printf("Node to right has more keys\n");
			goto done;
		}
		if(pkey->lcn->keys > mstore->min && pkey->lcn != bnod) {
			printf("Node to left has more keys\n");
			goto done;
		}
	}

done:
	bnod->keys--;
	free(key->data);
	return 0;
}
